package com.zhz.leetcode;

import com.zhz.leetcode.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 98. 验证二叉搜索树
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 示例 1：
 * 输入：root = [2,1,3]
 * 输出：true
 * <p>
 * 示例 2：
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 * <p>
 * 提示：
 * <p>
 * 树中节点数目范围在[1, 104] 内
 * -231 <= Node.val <= 231 - 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ValidateBinarySearchTree98 {

    public static void main(String[] args) {
        ValidateBinarySearchTree98 m = new ValidateBinarySearchTree98();
//        TreeNode root = new TreeNode(2, new TreeNode(2), new TreeNode(2));
        TreeNode root = new TreeNode(5, new TreeNode(1), new TreeNode(4, new TreeNode(3), new TreeNode(6)));
        boolean res = m.isValidBST1(root);
        System.out.println(res);
    }

    /**
     * 需要注意，不只需要当前 节点的左右子树满足条件，还需要当前节点的左子树大于父节点的父节点
     * 例如这个情况他就不是二叉搜索树
     * ------5
     * -----/ \
     * ----4   6
     * -------/ \
     * ------3   7
     * 因为节点3小于父节点的父节点，也就是5，因此他不是二叉搜索树
     * <p>
     * 使用递归方式
     */
    public boolean isValidBST(TreeNode root) {
        return test(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }


    public boolean test(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        return test(root.left, min, root.val) && test(root.right, root.val, max);
    }

    /**
     * 使用迭代的方式处理
     * 利用中序遍历
     */
    public boolean isValidBST1(TreeNode root) {
        //来，先实现一波迭代中序遍历
        Stack<TreeNode> stack = new Stack<>();
        double min = Math.pow(-2,31);
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (curr.val <= min) {
                return false;
            }
            min = curr.val;
            curr = curr.right;
        }
        return true;
    }


}
